package com.sheng.leetcode.year2022.month12.day05;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author liusheng
 * @date 2022/12/05
 * <p>
 * 1687. 从仓库到码头运输箱子<p>
 * <p>
 * 你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。<p>
 * 给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight ，<p>
 * 其中 boxes[i] = [ports i, weight i] 。<p>
 * ports i 表示第 i 个箱子需要送达的码头， weights i 是第 i 个箱子的重量。<p>
 * portsCount 是码头的数目。<p>
 * maxBoxes 和 maxWeight 分别是卡车每趟运输箱子数目和重量的限制。<p>
 * 箱子需要按照 数组顺序 运输，同时每次运输需要遵循以下步骤：<p>
 * 卡车从 boxes 队列中按顺序取出若干个箱子，但不能违反 maxBoxes 和 maxWeight 限制。<p>
 * 对于在卡车上的箱子，我们需要 按顺序 处理它们，卡车会通过 一趟行程 将最前面的箱子送到目的地码头并卸货。<p>
 * 如果卡车已经在对应的码头，那么不需要 额外行程 ，箱子也会立马被卸货。<p>
 * 卡车上所有箱子都被卸货后，卡车需要 一趟行程 回到仓库，从箱子队列里再取出一些箱子。<p>
 * 卡车在将所有箱子运输并卸货后，最后必须回到仓库。<p>
 * 请你返回将所有箱子送到相应码头的 最少行程 次数。<p>
 * <p>
 * 示例 1：<p>
 * 输入：boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3<p>
 * 输出：4<p>
 * 解释：最优策略如下：<p>
 * - 卡车将所有箱子装上车，到达码头 1 ，然后去码头 2 ，然后再回到码头 1 ，最后回到仓库，总共需要 4 趟行程。<p>
 * 所以总行程数为 4 。<p>
 * 注意到第一个和第三个箱子不能同时被卸货，因为箱子需要按顺序处理（也就是第二个箱子需要先被送到码头 2 ，然后才能处理第三个箱子）。<p>
 * <p>
 * 示例 2：<p>
 * 输入：boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6<p>
 * 输出：6<p>
 * 解释：最优策略如下：<p>
 * - 卡车首先运输第一个箱子，到达码头 1 ，然后回到仓库，总共 2 趟行程。<p>
 * - 卡车运输第二、第三、第四个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。<p>
 * - 卡车运输第五个箱子，到达码头 3 ，回到仓库，总共 2 趟行程。<p>
 * 总行程数为 2 + 2 + 2 = 6 。<p>
 * <p>
 * 示例 3：<p>
 * 输入：boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount = 3, maxBoxes = 6, maxWeight = 7<p>
 * 输出：6<p>
 * 解释：最优策略如下：<p>
 * - 卡车运输第一和第二个箱子，到达码头 1 ，然后回到仓库，总共 2 趟行程。<p>
 * - 卡车运输第三和第四个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。<p>
 * - 卡车运输第五和第六个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。<p>
 * 总行程数为 2 + 2 + 2 = 6 。<p>
 * <p>
 * 示例 4：<p>
 * 输入：boxes = [[2,4],[2,5],[3,1],[3,2],[3,7],[3,1],[4,4],[1,3],[5,2]], portsCount = 5, maxBoxes = 5, maxWeight = 7<p>
 * 输出：14<p>
 * 解释：最优策略如下：<p>
 * - 卡车运输第一个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。<p>
 * - 卡车运输第二个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。<p>
 * - 卡车运输第三和第四个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。<p>
 * - 卡车运输第五个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。<p>
 * - 卡车运输第六和第七个箱子，到达码头 3 ，然后去码头 4 ，然后回到仓库，总共 3 趟行程。<p>
 * - 卡车运输第八和第九个箱子，到达码头 1 ，然后去码头 5 ，然后回到仓库，总共 3 趟行程。<p>
 * 总行程数为 2 + 2 + 2 + 2 + 3 + 3 = 14 。<p>
 * <p>
 * 提示：<p>
 * 1 <= boxes.length <= 10^5<p>
 * 1 <= portsCount, maxBoxes, maxWeight <= 10^5<p>
 * 1 <= ports i <= portsCount<p>
 * 1 <= weights i <= maxWeight<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/delivering-boxes-from-storage-to-ports">1687. 从仓库到码头运输箱子</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1687 {

    @Test
    public void test01() {
        int[][] boxes = {{1, 1}, {2, 1}, {1, 1}};
        int portsCount = 2, maxBoxes = 3, maxWeight = 3;
//        int[][] boxes = {{1,2},{3,3},{3,1},{3,1},{2,4}};
//        int portsCount = 3, maxBoxes = 3, maxWeight = 6;
//        int[][] boxes = {{1,4},{1,2},{2,1},{2,1},{3,2},{3,4}};
//        int portsCount = 3, maxBoxes = 6, maxWeight = 7;
//        int[][] boxes = {{2,4},{2,5},{3,1},{3,2},{3,7},{3,1},{4,4},{1,3},{5,2}};
//        int portsCount = 5, maxBoxes = 5, maxWeight = 7;
        System.out.println(new Solution().boxDelivering(boxes, portsCount, maxBoxes, maxWeight));
    }
}

class Solution {
    public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
        /**
         * boxes[i] = {x, y}，x 代表要送到的码头，y 代表箱子重量
         * portsCount：码头数量
         * maxBoxes：箱子数量
         * maxWeight：重量限制
         */
        int n = boxes.length;
        // p[i] 初始值为 boxes[i - 1][0] 的值，即箱子要送到的码头
        int[] p = new int[n + 1];
        // w[i] 初始值为 boxes[i - 1][1] 的值，即箱子的重量
        int[] w = new int[n + 1];
        int[] neg = new int[n + 1];
        // W[i] 代表第 i 次运输和之前运输箱子的总重量之和
        long[] W = new long[n + 1];
        for (int i = 1; i <= n; ++i) {
            // 赋初始值
            p[i] = boxes[i - 1][0];
            w[i] = boxes[i - 1][1];
            // 从第二次运输开始
            if (i > 1) {
                // 第二次运输为前一次运输加上 (p[i - 1] != p[i] ? 1 : 0) ： 如果当前码头和上一次的码头相等则 + 0，否则 + 1
                neg[i] = neg[i - 1] + (p[i - 1] != p[i] ? 1 : 0);
            }
            // w[i] 加上之前运输的箱子的总重量 W[i - 1]，赋值给 W[i]
            W[i] = W[i - 1] + w[i];
        }
        // 创建队列 opt
        Deque<Integer> opt = new ArrayDeque<>();
        // 在队列尾部添加元素 0
        opt.offerLast(0);
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        // 循环
        for (int i = 1; i <= n; ++i) {
            // i - 队列队首的元素大于最大箱子数，或者箱子总重量 W[i] - 队首元素对应的箱子总重量大于最大重量时
            while (i - opt.peekFirst() > maxBoxes || W[i] - W[opt.peekFirst()] > maxWeight) {
                // 移除队首元素
                opt.pollFirst();
            }
            // f[i]
            f[i] = g[opt.peekFirst()] + neg[i] + 2;
            // 如果 i 不等于 n，即还没循环到最后一个箱子时
            if (i != n) {
                // g[i]
                g[i] = f[i] - neg[i + 1];
                while (!opt.isEmpty() && g[i] <= g[opt.peekLast()]) {
                    // 移除队尾元素
                    opt.pollLast();
                }
                // 将 i 元素添加到队尾
                opt.offerLast(i);
            }
        }
        return f[n];
    }
}
